Method of Processing Animation by Interpolation Between Key Frames with Small Data Quantity
1. Field of the Invention
The present invention relates to an animation processing method for recording or transmitting data of an animation previously created by the technique of computer graphics or the like, and more particularly, it relates to a method of compressing key frame information for displaying an animation by generating intermediate frames between pieces of key frame information by interpolation on the basis of images on frames (key frames) serving as keys in a time series, reducing the quantity of data for recording or transmission, and regenerating the animation in real time.
2. Description of the Background Art
Moving image data such as those forming an animation consist of an extremely large number of images called frames. In order to record information of the respective frames as such, an enormous data capacity is necessary. Thus, there has been proposed the so-called video compression for compressing the data of such video information with minimum reduction of the information quantity and recording or transmitting the same.
In case of inputting dynamic images from a camera or outputting the same onto a display, the so-called raster scan technique is generally employed. The raster scan technique is adapted to decompose each frame into a plurality of horizontal scan lines, for successively scanning the respective scan lines downward from above and rightward from the left. Therefore, the technique of video compression is generally directed to raster scan images.
An animation created by the technique of computer graphics is also converted to scan line information by the raster scan technique when displayed. In case of recording data of such an animation, a method of compressing a plurality of raster scan images is employed for recording the same in general. For example, Japanese Patent Laying-Open No. 61-198877 (1986) discloses a data compression technique of improving compressibility through conditions specific to a computer animation, for compressing scan line information by the raster scan technique.
On the other hand, techniques of creating animations by computer graphics include that called key frame animation. In this key frame animation, an animation is grasped as a set of a plurality of temporally changing xe2x80x9cobjectsxe2x80x9d. In case of creating an animation, not all frames but only frames (called xe2x80x9ckey framesxe2x80x9d) forming key points of the motion are created. Then, objects of frames (called xe2x80x9cintermediate framesxe2x80x9d) other than the key frames are automatically created by interpolative calculation of objects contained in the key frames. This interpolation method is disclosed in Japanese Patent Laying-Open No. 60-191366 (1985).
The animation created by this key frame technique can be regenerated from information related not to all frames but to only partial key frames. Therefore, the data quantity is advantageously remarkably reduced as compared with the case of creating information of all frames and recording the animation. Thus, the capacity of a necessary storage medium can be reduced and the transmission time can also be reduced, for example.
In order to automatically create intermediate frames from information of key frames by interpolation, required is information as to which object changes to what object. Therefore, the aforementioned Japanese Patent Laying-Open No. 60-191366 discloses a technique of mapping of objects. Data related to such mapping must also be recorded/transmitted along with the information of key frames.
FIGS. 1A to 1D show four key frames of a certain animation along a time series. Description is now made on how to record information on objects contained in the key frames of the animation shown in FIGS. 1A to 1D in the prior art.
Referring to FIGS. 1A to 1D, objects A0 to A2, B0 to B3, E2 and E3 are painted polygons. On the other hand, objects C1, C2 and D1 to D3 are curves. It is assumed that the key frames shown in FIGS. 1A to 1D are presented at times t0, t1, t2 and t3 in the animation respectively.
As understood from FIGS. 1A to 1D, the objects A0, A1 and A2 show changes of a single object. This object is referred to as an object A. Similarly, the objects B0 to B3 show changes of a single object B. The objects E2 and E3 show changes of a single object E. The objects C1 and C2 show changes of a single object C, and the objects D1 to D3 show changes of another single object D respectively.
In order to record information on objects contained in key frames, it is necessary to previously prepare data (state information) indicating in what states respective objects are in respective frames, as disclosed in Japanese Patent Laying-Open No. 5-101160 (1993), for example, as shown in FIG. 2 in the form of a table, for example. The full text of Japanese Patent Laying-Open Gazette No. 5-101160 is invoked here by reference.
Referring to FIG. 2, the respective columns indicate the key frames correpsonding to the respective times, and the respective rows correspond to the objects appearing in the animation. The respective elements in the table shown in FIG. 2 indicate state information of the respective objects in the key frames. For convenience of illustration, it is assumed that symbols A0 to A2, B0 to B3, C1, C2, D1 to D3, E2 and E3 denoting the respective objects also indicate the state information of the objects A to E at the respective times. In the table shown in FIG. 2, further, blank spaces show that the objects do not appear on the screen at the times.
Graphics appearing in the animation are assumed as the objects A to E in this case. However, the objects may be in various formats other than graphics. In addition to graphics such as lines, polygons, circles and stereoscopic figures, the objects may be characters, volumes of sounds or music, parameters of picture quality, positions and sizes of display windows, thicknesses of lines, colors, positions of light sources, positions of viewpoints and the like.
In order to provide sound effects in a certain key frame, for example, the sound effects are introduced into this key frame as objects. In order to change the position or size of a window for displaying the animation in a certain key frame, window parameters therefor are introduced into the key frame. Thus, all various numeric parameters employed in the animation can be treated as xe2x80x9cobjectsxe2x80x9d in this specification, particularly as state values indicating the states of the objects.
When the data shown in FIG. 2 in the form of a table are previously prepared, images of an intermediate frame at an arbitrary time can be calculated by interpolating state information of objects described in key frame information on key frames around the time such as a pair of or a plurality of preceding and succeeding frames. This interpolation method is disclosed in Japanese Patent Laying-Open No. 61-191366. Well-known techniques of interpolative calculation include an interpolation method employing linear interpolation or curve approximation of spline curves or the like.
FIGS. 5A to 5D show another exemplary animation related to the so-called business presentation. These figures show key frames respectively. Referring to FIGS. 5A to 5D, objects F0 to F3, forming an object F which is the background image, remain in the same state in all key frames. Objects G1 to G3, forming an object G consisting of characters xe2x80x9cpresentationxe2x80x9d, remain in the same state in the three key frames shown in FIGS. 5B to 5D. Objects H2 and H3, forming an object H consisting of characters xe2x80x9citem 1xe2x80x9d, are with colored and white background images respectively. An object I3, forming an object I consisting of characters xe2x80x9citem 2xe2x80x9d, is displayed only in the key frame shown in FIG. 5D, with a colored background image.
FIG. 6 shows key frame information for regenerating the animation shown in FIGS. 5A to 5D in the form of a table similarly to FIG. 2. The relation between FIG. 6 and FIGS. 5A to 5D is similar to that between FIG. 2 and FIGS. 1A to 1D. Therefore, redundant description is omitted.
With reference to FIG. 11, the conventional interpolation method proposed in Japanese Patent Laying-Open No. 60-191366 is now described. It is assumed that graphics 162 and 164 shown in FIG. 11 belong to key frames which are adjacent to each other on the time base. The method disclosed in Japanese Patent Laying-Open No. 60-191366 is adapted to equally divide the time between the graphics 162 and 164 of the adjacent key frames into n, and obtain respective corresponding points in images of intermediate frames 166, 168 and 170 (it is assumed that n =3) by linear interpolation between the corresponding image graphics 162 and 164 in the key frames. Assuming that the time base progresses along arrow in FIG. 11, the key frame containing the graphic 162, the three intermediate frames containing the intermediate graphics 166, 168 and 170, and the key frame containing the graphic 164 are displayed in this order for regenerating the animation. After the display of the key frame containing the graphic 164, similar interpolative calculation is performed between this key frame and the next key frame, for regenerating the animation.
This animation regenerating method has such an advantage that the data quantity necessary for animation regeneration can be by far reduced as compared with the case of having information of all frames. In general, therefore, all items of the data shown in FIG. 2 are simply recorded/transmitted for recording/transmitting the animation by the key frame method.
FIGS. 12A and 12B illustrate a conventional recording format. For example, the data shown in FIG. 2 are recorded/transmitted as animation data shown in FIG. 12A. Referring to FIG. 12A, each time ti and state information of each object in the key frame corresponding thereto are recorded/transmitted. Arbitrary symbol x indicating absence of objects is recorded/transmitted to a portion containing no corresponding object in each key frame. The time of each key frame and symbol indicating absence of objects can be recorded/transmitted in various expressing methods. For example, the time may be expressed in a numerical value in the unit of 1/1000 sec., while a specific code may be employed for symbol x.
On the other hand, state information of objects can be expressed through commands, for example. Exemplary state information of a painted polygon and that of a curve expressed in code trains respectively are as follows:
(Example of Painted Polygon)
P c, p, n, x1, y1, x2, y2, . . . , xn, yn where P represents a command indicating that this is a painted polygon, c represents the color number of the polygon, p represents the number of the paint pattern, n represents the number of points of the polygon, and x1, y1, x2, y2, . . . , xn, yn represent the coordinates of apices of the polygon. It is assumed here that various paint patterns are previously registered on a device side.
(Example of Curve)
W c, w, n, x1, y1, x2, y2, . . . , xn, yn where W represents a command indicating that this is a curve, c represents the color number of the curve, w represents the thickness of the curve, n represents the number of points of the curve, and x1, y1, x2, y2, . . . , xn, yn represent the coordinates of the points expressing the curve.
As hereinabove described, various numerical parameters for objects conceivable in addition to graphics can be coded in the format with heads of commands identifying the parameters respectively.
In another method, the information shown in FIG. 2 is recorded/transmitted with delimiters (e.g., xe2x80x9c,xe2x80x9d) between the respective data items, as shown in FIG. 12B. In this case, no symbol xe2x80x9cxxe2x80x9d is necessary for indicating absence of objects, while the delimiters must be recorded/transmitted in addition.
In the animation for the so-called business presentation shown in FIGS. 5A to 5D among animations, the screen itself generally remains rather unchanged but new items are successively added to the screen. In order to record such an animation in the aforementioned key frame animation method, objects once appearing on the screen must be recorded in all subsequent key frames as object information, even if these objects remain absolutely unchanged. This is a matter of course since all states of objects at times forming key points must be recorded due to the interpolation between adjacent key frames. When this recording system is employed, however, the data quantity is extremely increased. Particularly when the state information of each object is large data, the necessary data quantity is acceleratingly increased since the storage capacity necessary for recording the animation information is conceivably proportionate to the product of the number of the key frames and the data quantity per object.
In the animation shown in FIGS. 8A to 8D on the other hand, data must be recorded for every key frame even for an object having the same shape as a previously appearing object. Also in this case, the storage capacity necessary for recording the animation information is extremely increased, similarly to the animation for the so-called business presentation.
Such a problem applies not only to the case of recording animation information, but to the case of transmitting the information to another computer through a network.
Also as to objects appearing only in partial key frames, some information must be recorded/transmitted for indicating that these objects are absent in the remaining key frames, leading to wasteful recording/transmission. Every time a new key frame is added, for example, state information of objects not appearing at this point of time must be newly recorded/transmitted as blanks. The quantity of such data is accumulatively increased as the number of recorded/transmitted data is increased.
It has formerly been difficult to implement such an animation regenerating method itself. Due to the recent enhancement of the throughput of CPUs (central processing units), however, this animation regenerating method is now being implemented. In this method, however, a CPU generates intermediate frames by operations, and hence the following problems arise in addition to the problem of the data quantity:
With reference to FIG. 13, it is assumed that three frames 182, 184 and 186 correspond to the intermediate frames in the aforementioned conventional method. It is also assumed that the time required for plotting is 0.1 sec. as to each frame. Namely, a time of 0.3 sec. in total is necessary for regenerating these three frames 182, 184 and 186. When this animation is regenerated concurrently with sounds in real time, the following problems arise:
The first problem arises when this animation is regenerated in a CPU whose processing speed is lower than that assumed in creation of the animation. In this case, a time of 0.12 sec., for example, longer than 0.1 sec. is necessary for plotting one frame, as shown in FIG. 14. If frames 192, 194 and 196 are successively regenerated, therefore, the regeneration takes a time longer than that assumed therefor, and the delay from the regeneration time assumed at the start is gradually increased. On the other hand, the sounds are regenerated in the time assumed at the start. Consequently, the displacement between the motions of the displayed graphics and the sounds is gradually increased. For example, the shapes of the mouth of the person regenerated on the screen are displaced from the sounds along the frames 192, 194 and 196 as shown in FIG. 14.
The second problem arises when this animation is regenerated by a CPU having higher throughput than that assumed in creation of the animation, contrarily to the first problem. In this case, a time necessary for plotting each of frames 202, 204 and 206 may be only 0.06 sec., for example, i.e., shorter than 0.1 sec., as shown in FIG. 15. Therefore, the regeneration time for the animation is shorter than that assumed in creation of the animation. If the sounds are regenerated at a constant speed, the motions are displaced from the sounds also in FIG. 15. In this case, the motions of the animation are faster than the sounds.
The aforementioned problems are caused due to the difference in throughput of the CPUs. However, such problems are also caused by fluctuations of the plotting quantity required per frame. Referring to FIG. 16, for example, consider that the size of plotted graphics is increased on the time base along frames 212, 214 and 216. In this case, the time required for plotting is increased as the graphic size is increased. For example, it is assumed that times of 0.1 sec., 0.11 sec. and 0.12 sec. are necessary for plotting the frames 212, 214 and 216 respectively. Also in this case, a delay of 0.01 sec. results in the frame 214, and a delay of 0.01+0.02=0.03 sec. results in the frame 216. Therefore, the timing for generating each frame is displaced from that for regenerating the sound also in this case.
In order to solve such problems related to synchronization of the sounds and the screen, starting times for plotting the respective frames may be decided with reference to the head frame. In this system, however, the following problem arises in the example shown in FIG. 13:
Referring to FIG. 17, consider that the throughput of the CPU is lower than the assumed one. In this case, the plotting time allocated to each of three frames 222, 224 and 226 is decided as 0.1 sec., for example. If the processing speed of the CPU is slow, it may be impossible to completely plot each graphic in the supplied plotting time. In this case, plotting of the next frame is disadvantageously started despite incomplete plotting of each frame, as shown in the frame 222, 224 or 226 in FIG. 17.
If the throughput of the CPU is higher than the assumed one, on the other hand, the following problem arises: If respective frames 232, 234 and 236 shown in FIG. 18 are regenerated by such a CPU having high throughput, only a time of 0.06 sec. is necessary for plotting each frame, for example. The time allocated for plotting of each frame is 0.1 sec. Therefore, a pause of 0.04 sec. results after completion of plotting of each frame, and the CPU is in idle during this pause. In case of making the best use of the throughput of the CPU, it must be possible to regenerate not only the three frames 232, 234 and 236 shown in FIG. 18 but five frames 242, 244, 246, 248 and 250, for example, as shown in FIG. 19. The motions of the animation are smoothed as the number of frames regenerated in a unit time is increased, and hence the pauses shown in FIG. 18 are preferably minimized so that the frames are regenerated as shown in FIG. 19.
Further, such animation regeneration is preferably applicable not only to the positions and sizes of the graphics but to colors and degrees of transparency of the graphics, thicknesses of lines forming the graphics, ratios of plotted parts to unplotted parts in broken lines, for example, forming graphics, font sizes in case of displaying characters, and the like. Similar processing can preferably be performed on movement of not only a single graphic but a graphic group consisting of a group of basic graphics. This also applies to scale percentage for displaying the group. Further, it is more preferable if an animation can be regenerated not only with simple motions but with specific changes with respect to progress of time in creation of intermediate frames from key frames.
Accordingly, an object of the present invention is to provide an animation processing method which can reduce the quantity of treated data in data processing of an animation in a key frame system, while keeping the quantity of information related to the animation.
Another object of the present invention is to provide an animation processor which can reduce the quantity of treated data in data processing of an animation in a key frame system, while keeping the quantity of information related to the animation.
Still another object of the present invention is to provide a compression method for animation information which can more efficiently compress animation information employing a key frame animation system.
An additional object of the present invention is to provide an animation regenerating method which can regenerate an animation by generating as many intermediate frames as possible between key frames while keeping a constant regeneration speed for the animation.
A further object of the present invention is to provide an animation regenerating method which can change motions of an animation in a key frame system.
The animation processing method according to the present invention is adapted to process an animation consisting of at least one object having a changeable state, and comprises a time information output step of outputting a time for presenting a key frame on the animation to a predetermined medium for every key frame, and a state information recording/transmission step of outputting state information of each object appearing in the key frame to the predetermined medium in correspondence to the time information of the key frame outputted by the time information output step for every key frame. The predetermined medium may be either a storage medium or a communication medium.
In this animation processing method, the information on the time for presenting the key frame on the animation and the state information of only each object appearing in the key frame are recorded or transmitted for every key frame by the time information and state information output steps, whereby no information is recorded or transmitted in relation to objects not appearing in the key frame. In other words, no unnecessary data are recorded or transmitted in relation to objects not appearing in the key frame. In relation to recording or transmission of the animation, the quantity of recorded or transmitted data can be reduced while preserving the information quantity of the animation. Consequently, the memory capacity for recording the animation data can be saved while high-speed data transmission is enabled.
Preferably, the animation processing method according to the present invention includes a link information output step of recording or transmitting link information as to each object appearing in the key frame and that in another key frame in correspondence to the state information of the object recorded or transmitted through the state information output step for every key frame.
The link information is further recorded or transmitted in correspondence to the state information of each object, whereby presence/absence of a certain object in a certain frame can be determined by whether or not an object linked with this object is present in a related key frame. No object information on an absent object may be included in the key frame information, whereby the data quantity can be further reduced.
According to another aspect of the present invention, an animation display method, which is adapted to display an animation of graphics on a display unit through a computer program, includes steps of preparing a plurality of pieces of key frame information each including information for specifying a display time and graphic information for specifying the features of a graphic to be displayed in a display frame at the display time, obtaining a current time for display, selecting at least two pieces of key frame information having display times before and after the obtained current time for display in the aforementioned plurality of pieces of key frame information, performing prescribed interpolative calculation between corresponding pieces of graphic information included in at least two pieces of key frame information respectively thereby creating graphic information to be displayed at the obtained current time for display, plotting a frame at the obtained current time for display on the basis of the created graphic information, and repeating the aforementioned step of obtaining the current time for display, the selecting step, the creating step and the displaying step up to a lapse of a prescribed time.
After a plurality of pieces of key frame information are previously prepared in a memory, the following operations are repeated: First, a current time for display is obtained. Two pieces of key frame information having times before and after the current time are selected. Prescribed interpolative operation is performed between corresponding pieces of graphic information included in the two pieces of key frame information, for creating graphic information to be displayed at the current time for display and plotting the graphic. No graphic information for the next frame is created until one frame is entirely plotted, whereby each frame can be completely plotted. Further, no display time is previously decided, whereby the animation can be displayed in response to the ability of a CPU, so that a CPU having high throughput creates a number of intermediate frames while that having low throughput creates a small number of intermediate frames.
Preferably, the plurality of pieces of key frame information include head key frame information related to a frame to be displayed at the head in this animation display method. This animation display method further includes a step of displaying the head frame in starting of the animation display, on the basis of the head frame information. Further, the step of obtaining the current time for display includes a step of referring to a timer in response to completion of plotting of one frame and obtaining the current value of the timer as the current time for display.
When the head frame is completely plotted, a current time for display of the next frame is obtained in response to this completion. When the frame is completely plotted at this time, a current time for next display is further obtained in response to this completion. Thus, when certain frames are successively completely plotted, frames are repeatedly created and plotted for display at the times of the completion. Thus, it is possible to make the best use of the ability of the CPU with no idle time.
The graphic information includes coordinate information on feature points of each graphic, color information of each graphic, information on the degree of transparency of each graphic, information on the thickness of lines forming each graphic, information on the ratio of plotted parts to unplotted parts of the lines forming each graphic, the size of each character font, coordinates of reference points of a graphic group, and scale percentage of the graphic group on display respectively. The graphic information may include deformation or movement of each graphic, a change in the color of each graphic, a change of the degree of transparency of each graphic, the thickness of lines forming each graphic, the mode of broken lines forming each graphic, the size of each character font, movement of a graphic group, or scale percentage of the graphic group on display, by creating and plotting graphic information in intermediate frames by interpolative operation between such pieces of graphic information.
More preferably, the creating step of the animation display method includes steps of performing interpolative calculation by prescribed linear calculation between corresponding pieces of graphic information included in two pieces of key frame information respectively, and converting graphic information obtained by this interpolative calculation by a predetermined conversion method.
A motion which is nonlinear with respect to time such as a motion accompanied by acceleration, for example, can be expressed by further converting graphic information once created by such interpolative calculation by linear calculation. Namely, changes can be obtained on the time base in the animation.
The converting step may include a step of looking up converted graphic information corresponding to the graphic information created in the creating step in a table. Graphic information once created by interpolative calculation is converted through the table for displaying the animation by the converted graphic information. An arbitrary change on the time base can be implemented on the animation.
Alternatively, the converting step may include a step of substituting the graphic information created in the creating step for a variable of a prescribed function and regarding the value of this function as the converted graphic information.
The graphic information obtained by the interpolative calculation by linear calculation is further substituted for the variable of the prescribed function to be converted, whereby a nonlinear motion can also be implemented on the animation. Further, the quantity of data necessary therefor can be reduced.
According to still another aspect of the present invention, the compression method for animation information is adapted to compress key frame information for an animation whose intermediate frames are generated and displayed by interpolation between a plurality of key frames through a computer. Each key frame information includes object information related to an object to be displayed in the corresponding key frame. The object information includes state information of the object, and link information to corresponding object information in key frame information having a predetermined relation with this key frame information. This method comprises a first output step of loading reference key frame information and outputting the same to a medium, a second output step of loading next key frame information in response to completion of outputting of just preceding key frame information, comparing each object information in the loaded key frame information with corresponding object information in key frame information having a predetermined relation with the loaded key frame information, and outputting compressed key frame information including object information including link information and state information having discrepancy with respect to the medium, and a step of repeating the second output step up to compression of all key frame information to be compressed.
The object information of the compressed key frame information includes link information and state information having discrepancy. The compressed key frame information includes no state information having no discrepancy with respect to that of the key frame compared therewith. However, the same can be restored from the compared key frame information in regeneration of the animation. Therefore, the animation can be regenerated from animation information of a smaller data quantity as compared with the conventional case of recording all state information as to each object information of each key frame.
Preferably, the key frame information having a predetermined relation in the compression method for animation information is key frame information outputted just in advance of the key frame information. The key frame information outputted just in advance is successively compared with the key frame information to be processed, for outputting key frame information including object information including only state information having discrepancy. The key frame information may simply be compared with the just preceding key frame information, whereby the storage capacity required for the processing can be reduced. The feature of the animation resides in that the number of objects changing states is generally small between adjacent key frames. Therefore, it is expected that the quantity of state information to be outputted is relatively reduced by comparing the just preceding key frame with the key frame to be processed, whereby the data quantity of the animation information can be reduced.
Preferably, the object information may further include a quantity of discrepancy as to the state information having discrepancy. State information having no discrepancy is not necessarily included. According to this method, therefore, the data quantity of the animation information can be by far reduced as compared with the prior art.
Preferably, the second output step includes steps of loading next key frame information in response to completion of outputting of just preceding key frame information and retrieving key frame information including object information which is in a relation of translation with each object information the loaded key frame information, and outputting compressed key frame information including object information including information specifying the key frame information including the object information having the relation of translation, link information and a translation quantity to the medium.
According to this method, the object information of the compressed key frame information includes the link information, the information specifying the key frame information including the object information of an object having the relation of translation with an object corresponding to the object information, and the translation quantity. Coordinate information of the object in the key frame to be processed can be restored from the object information of the object having the relation of translation and the translation quantity. The quantity of necessary data is reduced as compared with the case of recording all coordinate information of the object in the object information. The animation has such a feature that the translation quantity between the objects having the relation of translation is generally smaller than the values of the coordinates of the objects themselves. According to this method, therefore, the data quantity of the animation information can be by far reduced as compared with the conventional method.